算法专题二、DFS + BFS
Algorithm-DFS
Algorithm-BFS
Algorithm-Conclusion
05/10/2021
前言
自己在 LC 上陆陆续续刷了 300 题了，但是没有对他们进行系统的整理总结，对各种类型的题目及其解法总感觉不够清晰明了，所以最近希望把算法好好整理一下，按各个类型进行专题整理，先总结知识点，再找对应题目进行专项练习
本章是第二专题—— DFS + BFS
概述
关于算法策略总结，可以看我的另一篇博客
按照那篇文章总结的算法策略分类，DFS（Depth-First-Search） 应当属于递归回溯策略：
类似于枚举，通过尝试遍历问题各个可能解的通路，当发现此路不通时，回溯到上一步继续尝试别的通路。
其实 DFS 就可以理解成递归的一种，如果从树状结构出发，DFS 大多数时候就是从根节点一直像下遍历，直到走到叶节点，完成一条路径的探索，再根据条件判断，是否需要回溯。
容易想到，递归的函数形成了函数栈，因此如果我们要实现非递归方式的 DFS，就是用栈来做到
广义的 DFS 可以拓展到图论中，用于对图的连通性进行测试，典型的问题：迷宫连通性测试、图的条件搜索等
- BFS（Breadth-First-Search），和 DFS 很类似，也是一种搜索算法，但是和 DFS 不同，BFS 从另一个维度进行“递归”——横向。以树状结构为例，BFS 会遍历当前节点下所有的子节点，排除不符合条件的节点再继续向下探索，打个比方，如果 DFS 是一头走到底的莽夫，BFS 就类似于每走一步就小心翼翼确认方向的智者。因此，事实上，大部分时候遇到 DFS 会 TLE 的题目，需要用 BFS 进行剪枝处理，不然空间复杂度太大。
因为 BFS 是逐层遍历，符合 FIFO（先进先出），因此如果实现非递归的版本，需要用队列实现
DFS 题目
全排序类题目
- 46. 全排列：给定一个 没有重复 数字的序列，返回其所有可能的全排列。
- 47. 全排列 II：给定一个 有重复 数字的序列， 按任意顺序 返回所有不重复的全排列。
- 面试题 08.07. 无重复字符串的排列组合：计算某字符串的所有排列组合，字符串每个字符 均不相同。
- 面试题 08.08. 有重复字符串的排列组合：计算 有重复 字符串的所有排列组合，输出结果中不能有重复的字符串。
- 剑指 Offer 38. 字符串的排列：虽然题干不太一样，但是代码可以直接 用上一题的。
- 60. 排列序列：原名为第 k 个排序，难度较大，笔试更可能遇到。此题可以使用 dfs+剪枝，推荐@liweiwei1419 的题解：深度优先遍历 + 剪枝、有序数组模拟
- 784. 字母大小写全排列：给定一个字符串 S，通过将字符串 S 中的每个字母转变大小写获得一个新的字符串，返回所有可能得到的字符串集合。 提升：可以在本地编译环境试试将所有输出结果按 字典序排列 或者 逆字典序排列。
组合类题目
- 17. 电话号码的字母组合：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
- 77. 组合：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
- 39. 组合总和：给定一个 无重复元素 的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以 无限制重复被选取 。
- 40. 组合总和 II：给定一个数组 candidates （ 数组中的数字可能重复）和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中 只能使用一次。
- 216. 组合总和 III：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1-9 的正整数，并且每种组合中不存在重复的数字。
- 377. 组合总和 Ⅳ：给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。PS：这题不用 DFS，而是用动态规划，放在此处只是因为题目名字相似。
子集类题目
- 78. 子集：给定一组 不含重复元素 的整数数组 nums，返回该数组所有可能的子集（幂集）。
- 90. 子集 II：给定一个 可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
- 面试题 08.04. 幂集：跟上一题除了函数名不一样以外，其余代码可以一模一样。 提升：可以在本地编程环境试试将整数数组改成字符数组，并且最后的结果按任意、字典序或者逆字典序顺序排列。
单词搜索类题目
- 79. 单词搜索：给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
- 剑指 Offer 12. 矩阵中的路径：别看此题题干好多字的样子，实际上代码和上一题一模一样，连函数名都没变。
- 212. 单词搜索 II：个人觉得难度不适合普通面试者的面试，但是笔试时候很有可能考到。（本人遇到 2-3 次与此题类似的笔试题）
BFS 题目
给定网格的题目
方法很多，例如：DFS、BFS 和并查集。
- 被围绕的区域：给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。 这题可以用的方法很多，常见的有 DFS、BFS 和并查集，其中并查集这种数据结构看似不经常用，实际上分析此类题目时候会发挥比较好的作用。
- 岛屿数量：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 同样也是可以用多种方法的一题。提升：可以思考下如果输入的不是 char，而是 int 的话，该怎么处理。
- 岛屿的最大面积：给定一个包含了一些 0 和 1 的非空二维数组 grid。一个岛屿是由一些相邻的 1(代表土地)构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。 面试题 16.19. 水域大小：你有一个用于表示一片土地的整数矩阵 land，该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。 提升：做完可以与上一题对比下异同点。
- 地图分析：你现在手里有一份大小为 NxN 的网格 grid，上面的每个单元格都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
- 腐烂的橘子：每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。
拓扑排序的题目
不算 BFS，只是思路类似。
- 课程表：你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0，你需要先完成课程 1，我们用一个匹配来表示他们：[0,1]。给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
- 课程表 II：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0，你需要先完成课程 1，我们用一个匹配来表示他们: [0,1]。给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。 提升：本地编译环境试试返回所有正确的顺序。（返回值类型改变）
- 课程表 III：这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。给出 n 个在线课程用(t, d)对表示。你的任务是找出最多可以修几门课。 此题可以用拓扑排序，但是可能贪心更方便，题目较难，放在这就是为了系列题好看而已，看不懂的建议直接跳过。
染色的题目
不算 BFS，只是思路类似。
- 图像渲染：有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。 面试题 08.10. 颜色填充：题目名称和题目叙述与上一题不太一样，代码可以一模一样。
- 不邻接植花：有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。另外，所有花园最多有 3 条路径可以进入或离开。你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。 本质上也是个染色问题。
并查集的题目
官方题解写的 399. 除法求值，这篇题解的最后列了很多类似的练习题，学有余力的同学可以做一下哈。
备注：这类题目在笔试中可能较高频率出现，在面试中通常是面试官水平比较高且觉得面试者水平比较高的时候才可能给面试者出。
参考连接
- LeetCode DFS 专题总结
- DFS 总结
- 个人更多算法总结在Github
